package com.xiaoyu.linkedArray;

/**
 * @program: DS_and_A
 * @description: 两两交换!
 *
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 *
 * @author: YuWenYi
 * @create: 2021-06-02 10:21
 **/
public class SwapPairs {

    //交换引用
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0,head);
        ListNode res = dummy;
        while (dummy.next != null && dummy.next.next != null){
            ListNode tail = dummy.next.next;
            ListNode next = dummy.next;
            dummy.next = tail;
            next.next = tail.next;
            tail.next = next;
            dummy = next;
        }
        return res.next;
    }

    //换值很简单
    public static ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = head;
        while (dummy!=null && dummy.next != null){
            int temp = dummy.val;
            dummy.val = dummy.next.val;
            dummy.next.val = temp;
            dummy = dummy.next.next;
        }
        return head;
    }

    //解法三:使用递归
    public static ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //一共三个节点:head, next, swapPairs(next.next)
        //下面的任务便是交换这3个节点中的前两个节点
        ListNode next = head.next;
        //swapPairs(next.next);就是处理完的结点,将头的next指向它,然后将next的next指向头就完成了交换
        head.next = swapPairs(next.next);
        next.next = head;
        //根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
        return next;
    }



    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4,new ListNode(8,
                        new ListNode(7,new ListNode(6,new ListNode(5))))))));

        ListNode node = swapPairs2(head);
        ListNode.printList(node);
    }
}
